package com.kevin.Code.OfferReviewVersion2;

import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @author Vinlee Xiao
 * @Classname OneZeroMatrix
 * @Description 剑指Offer107 同Leetcode 542. 01矩阵 中等难度 考察图算法
 * @Date 2022/1/11 15:42
 * @Version 1.0
 */
public class OneZeroMatrix {

    /**
     * 广度优先遍历
     * 参考剑指Offer专项突破版题解思路
     *
     * @param mat
     * @return
     */
    public int[][] updateMatrix(int[][] mat) {

        int row = mat.length;
        int col = mat[0].length;
        //建立一个同样大小的二维矩阵
        int[][] dist = new int[row][col];
        //用于存储两个坐标
        Deque<int[]> deque = new ArrayDeque<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (mat[i][j] == 0) {
                    dist[i][j] = 0;
                    //将坐标添加进队列中
                    deque.addLast(new int[]{i, j});
                } else {
                    dist[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        //对应当前坐标的上下左右四个坐标
        int[][] position = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (!deque.isEmpty()) {
            int[] indexs = deque.removeFirst();
            int res = dist[indexs[0]][indexs[1]];

            for (int[] pos : position) {
                //新的行列坐标
                int r = indexs[0] + pos[0];
                int c = indexs[1] + pos[1];
                //新生成的坐标是否是在优先的范围之内
                if (r >= 0 && r < row && c >= 0 && c < col) {
                    //如果当前坐标上的值大于indexs的坐标值加1说明还没置为最小零值
                    //关键点:如何避免重复访问 当重复时值是相同的 不满足条件
                    if (dist[r][c] > res + 1) {
                        //将新的二维矩阵值置为
                        dist[r][c] = res + 1;
                        deque.addLast(new int[]{r, c});
                    }
                }
            }
        }

        return dist;
    }


}
